Modern computer networks often have many routers interconnected, and the routers route multicast packets from at least one source station to multiple destination stations. Additionally, the routers route ordinary data traffic in the computer network, and may route many different multicast sessions, each session originating from a different source station. Links of the network between routers may become congested from the traffic load which they are required to carry. When a link becomes congested, the packets may be discarded by a router, that is, the router may simply drop the packet rather than transmit it.
Congestion of a link is often caused by a transmitting queue in a transmitting router which sends packets to the link becoming full, so that there is no place in the transmitting queue to store the next packet to be transmitted. So, the next packet is simply discarded by the router rather than being transmitted.
Alternatively, a link may be congested because a receiving router has its receiving buffers filled, and that router is unable to store the packet as it arrives at the receiving router. The incoming packet is then simply discarded rather than being “received” by the receiving router.
It is desirable, when data files are transported over a computer network, to have all of the packets arrive at the destination station. Likewise, in a multicast session, after a destination station joins the multicast group, it is desirable that the destination station receive all subsequently transmitted multicast data packets.
Various multicast protocols use different methods to deal with loss of multicast packets. It is standard engineering practice for the multicast packets to carry a sequence number, and so a destination station can monitor the sequence numbers of the packets which it receives, and if any sequence number is missing, learn that the corresponding packet is missing. For example, some multicast protocols, such as PGM (full name, Pragmatic General Multicast) described in an Internet Draft which is posted on the Internet Engineering Task Force (IETF) website at www.ietf.org, use negative acknowledgement (NAK) messages transmitted by destination stations which do not receive a multicast packet. The NAK message requests re-transmission of the lost packet. For example, the source station receives a NAK message and then re-transmits the missing packet. Alternatively, designated repair stations receive the NAK message and re-transmit the missing packet.
In PGM an important mechanism reduces the number of NAK messages by, for example, having a router forward a NAK message requesting a particular missing packet only once, rather than forwarding each NAK message transmitted by each destination station for which the packet is lost, etc. The re-transmitted packet will also, ordinarily, pass through the congested link, thereby making a further contribution to congestion on that link.
In more detail, some multicast protocols, such as the PGM protocol, have routers eliminate NAK packets. A router remembers which sequence number of multicast group data packets it has recently requested, and in the event that a later NAK packet requests the same sequence number, the router does not transmit a duplicate NAK packet. By eliminating NAK packets, the routers guard against a problem known as “NAK implosion”, where a NAK packet from every destination station is transmitted to the source station. In the event that there are hundreds, or for example millions, of destination stations for the multicast group and a key link becomes congested, then perhaps millions of destination stations will be missing a packet with a particular sequence number. Each destination station missing the multicast group data packet transmits a NAK packet, and so millions of NAK packets may be transmitted by the destination stations. The source station would be overwhelmed by a million NAK packets requesting re-transmission of the same multicast group data packet. By eliminating the NAK packets, the routers avoid NAK implosion at the source station. The PGM specification describes elimination of NAK packets by the routers.
It is also standard engineering practice to have the source station reduce its transmission rate in response to receiving NAK packets. For example, both a leaky bucket algorithm and a token bucket algorithm are discussed in detail by Andrew Tanenbaum in his book Computer Networks, Third Edition, published by Prentice Hall, Copyright date 1996, all disclosures of which are incorporated herein by reference, especially at pages 374–395. A source end station may increase its transmission rate to a maximum transmission in the absence of receiving NAK packets, and then reduce its transmission in response to receiving the NAK packets through implementation of an algorithm such as the leaky bucket or token bucket algorithms. Again, in the absence of receiving NAK packets, the source end station increases its transmission rate until it again receives NAK packets. Using feedback from the intended destination end stations the source end stations raise and lower their transmission rate, in response to network conditions detected by the destination end stations. Further, in the PGM specification, a source station of a multicast session reduces its transmission rate in response to receiving NAK messages.
A disadvantage of relying on NAK messages to eliminate congestion is that if a packet is lost at an intermediate link delivering multicast packets to many destination stations, then each destination station will transmit a NAK message. These NAK messages consume a lot of network bandwidth, even though the number of upstream messages is reduced by selective forwarding, as is done in the PGM protocol. Further, in the event that the NAK messages are diverted to “repair stations”, the source station may not learn that it should reduce its transmission rate. Further, simply responding to NAK messages is a relatively crude way for the source station to learn that congestion is occurring in the network.
A further method presently used to avoid congestion by multicasting source end stations is the Resource reSerVation Protocol, the RSVP protocol. The RSVP protocol is described by Tanenbaum in his book Computer Networks, Third Edition at pages 393–395. In the RSVP protocol, source end stations reserve bandwidth through a multicast distribution tree which incorporates all members of the receiving group for the multicast session. A disadvantage of the RSVP protocol is that reservation of bandwidth through a multicast distribution tree requires heavy expenditure of resources for overhead, and a reservation of bandwidth method does not respond adequately to dynamic changes in conditions on the computer network.
There is needed a flexible method of congestion control for computer networks, especially a method which can handle multicast flows from a source end station to multiple destination stations, and can also respond dynamically to changes in the computer network.